package DFA

import (
	"sort"
	"strconv"
	"strings"
)

type state struct {
	sJoin   string // 表示字符串 由stat 连接形成
	name    string
	stat    []*node           //状态集
	trans   *map[byte][]*node //转移map
	mp      map[byte]string   //转移的节点的name
	groupId int               //组号
	groupMp map[byte]int      //组号转移map
}

// CreateDFA 从NFA中创建DFA
func CreateDFA(NFA NFA, charSet []byte) DFA {
	//初态集合
	var be = getEClosure([]*node{NFA.In()}, map[string]struct{}{})
	var beginStat = state{}
	beginStat.sJoin = getStringC(be)
	beginStat.name = "0"
	beginStat.stat = be

	var mp = make(map[string]string)
	var queue = make([]*state, 0, 100)
	mp[beginStat.sJoin] = "0"
	var id = 1
	queue = append(queue, &beginStat)

	for i := 0; i < len(queue); i++ {
		queue[i].trans = &map[byte][]*node{}
		queue[i].mp = map[byte]string{}
		for j := 0; j < len(charSet); j++ {
			var tem = getEClosureAny(charSet[j], queue[i].stat)
			if len(tem) == 0 {
				continue
			}
			(*queue[i].trans)[charSet[j]] = tem

			temS := getStringC(tem)
			//判断 tem组合是否已经出现过，出现过则无需加入queue
			if v, ok := mp[temS]; ok {
				queue[i].mp[charSet[j]] = v
			} else {
				// 创建新的state 加入queue
				var stTem = state{}
				stTem.stat = tem
				stTem.sJoin = temS
				stTem.name = strconv.Itoa(id)
				id++
				mp[temS] = stTem.name
				queue[i].mp[charSet[j]] = stTem.name
				queue = append(queue, &stTem)
			}

		}
	}

	//遍历 queue获取end集合
	var end = make([]*state, 0, 100)
	for i := 0; i < len(queue); i++ {
		for j := 0; j < len(queue[i].stat); j++ {
			if queue[i].stat[j] == NFA.Out() {
				end = append(end, queue[i])
				break
			}
		}
	}
	return DFA{queue, &beginStat, end, charSet}
}

// getEClosure 搜索 ε 闭包
func getEClosure(nods []*node, mp map[string]struct{}) []*node {
	var eNodes = make([]*node, 0, 100)
	for _, v := range nods {
		for _, v1 := range v.any {
			if _, ok := mp[v1.name]; !ok {
				eNodes = append(eNodes, v1)
				mp[v1.name] = struct{}{}
			}
		}

	}
	//递归搜索
	if len(eNodes) != 0 {
		eNodes = append(eNodes, getEClosure(eNodes, mp)...)
	}
	return eNodes
}

// getEClosureAny 获取状态子集
func getEClosureAny(b byte, nods []*node) []*node {
	var nodes = make([]*node, 0, 100)
	var mp = make(map[string]struct{})
	for _, v := range nods {
		if nodeT, ok := v.edges[b]; ok {
			if _, ok1 := mp[nodeT.name]; !ok1 {
				nodes = append(nodes, nodeT)
				mp[nodeT.name] = struct{}{}
			}
		}
	}
	nodes = append(nodes, getEClosure(nodes, mp)...)
	return nodes
}

// getString 合并nodes的名字获取唯一标识
func getStringC(nodes []*node) string {
	var strT = make([]string, 0, 100)
	for _, v := range nodes {
		strT = append(strT, v.name)
	}
	sort.Strings(strT)
	var sb = strings.Builder{}
	for _, v := range strT {
		sb.WriteString(v)
		sb.WriteByte('|')
	}
	return sb.String()
}

// SimplifyDFA  简化DFA
func SimplifyDFA(dfa DFA) DFA {
	//初始化 将状态分为两部分
	var id = 0
	for i := 0; i < len(dfa.states); i++ {
		if i < len(dfa.states)/2 {
			dfa.states[i].groupId = id
		} else {
			dfa.states[i].groupId = id + 1
		}
		dfa.states[i].groupMp = make(map[byte]int)
	}

	for {

		//状态名到组号的映射
		var mp = map[string]int{}
		for i := 0; i < len(dfa.states); i++ {
			mp[dfa.states[i].name] = dfa.states[i].groupId
		}

		//计算组转移map

		for i := 0; i < len(dfa.states); i++ {
			dfa.states[i].groupMp = map[byte]int{}
			for _, v := range dfa.charSet {
				if v1, ok := mp[dfa.states[i].mp[v]]; ok {
					dfa.states[i].groupMp[v] = v1
				}

			}
		}

		var id = 0
		var tem = make([]int, len(dfa.states)) //临时保存新组名
		//分组 相同标识的同一组
		var mp1 = map[string]int{} //分组映射
		for i := 0; i < len(dfa.states); i++ {
			var s = joinS(dfa.states[i].groupMp, dfa.charSet, dfa.states[i].groupId)
			if v, ok := mp1[s]; ok {
				tem[i] = v
			} else {
				tem[i] = id
				mp1[s] = id
				id++

			}
		}

		//判断新分组是否与原分组一致
		var flag = true
		for i := 0; i < len(tem); i++ {
			if dfa.states[i].groupId != tem[i] {
				flag = false
			}
			dfa.states[i].groupId = tem[i]

		}
		if flag {
			break
		}
	}
	//构建新的DFA
	var res = &DFA{}
	states := make([]*state, 0, 100)
	var mp2 = make(map[string]struct{})
	//将begin和end先放入
	var st = joinS(dfa.begin.groupMp, dfa.charSet, dfa.begin.groupId)
	mp2[st] = struct{}{}
	var t = cp(dfa.begin, dfa.charSet)
	res.begin = t
	states = append(states, t)

	for _, v := range dfa.end {
		var st = joinS(v.groupMp, dfa.charSet, v.groupId)
		if _, ok := mp2[st]; !ok {
			mp2[st] = struct{}{}
			t := cp(v, dfa.charSet)
			states = append(states, t)
			res.end = append(res.end, t)
		}
	}

	for _, v := range dfa.states {
		var st = joinS(v.groupMp, dfa.charSet, v.groupId)
		if _, ok := mp2[st]; !ok {
			t := cp(v, dfa.charSet)
			mp2[st] = struct{}{}
			states = append(states, t)
		}
	}
	res.states = states
	res.charSet = dfa.charSet
	return *res

}

// 从mp创建唯一标识
func joinS(mp map[byte]int, charset []byte, id int) string {
	var sb = strings.Builder{}
	sb.WriteString(strconv.Itoa(id))
	sb.WriteByte('|')
	for _, v := range charset {
		if b, ok := mp[v]; ok {
			sb.WriteString(strconv.Itoa(b))
		}
		sb.WriteString(" ")

		sb.WriteByte('|')
	}
	return sb.String()
}

// 转移复制 groupId -->name ,groupMp--> mp
func cp(state2 *state, keySet []byte) *state {
	var t = &state{}
	t.name = strconv.Itoa(state2.groupId)
	t.mp = make(map[byte]string)
	for _, v := range keySet {
		if val, ok := state2.groupMp[v]; ok {
			t.mp[v] = strconv.Itoa(val)
		}
	}
	return t
}
